package tree.searchTree.prefixTree;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 功能描述: 所有字符的前缀搜索树
 * 2024/05/25
 * <p>
 * ZhangYi
 *
 * 包括一个字符和一个指针 对应的是 包括一个字符和一个指针
 * 例如，每个节点占用16字节（包括一个字符和一个指针），10亿个字符串将占用约160GB的内存。65,535 个不同的字符。
 *
 */
public class PrefixTrieMapUtils {

    public static class Node{
        private int pass;
        private int end;

        private Map<Integer,Node> map;

        public Node() {
            this.pass = 0;
            this.end = 0;
            this.map = new HashMap<>();
        }
    }

    public static class TrieUtils{
        Node root = new Node();

        /**
         * 功能描述: 插入一个字符串
         *
         * @param word 字
         */
        public void insert(String word){
            if (word == null){
                return;
            }

            Node cur = root; // 指针从头结点开始移动
            char[] charArray = word.toCharArray();

            for (int i = 0; i < charArray.length; i++) {
                int intStr = (int)charArray[i];

                if (cur.map.get(intStr) == null){
                    cur.map.put(intStr,new Node());
                }

                cur.map.get(intStr).pass++;
                cur = cur.map.get(intStr);
            }

            cur.end++;
        }

        /**
         * 功能描述: 查找一个字符串
         *
         * @param word 字
         * @return int
         */
        public int search(String word){
            if (word == null){
                return 0;
            }

            Node cur = root; // 从根节点开始查找
            char[] charArray = word.toCharArray();
            for (char c : charArray) {
                int intStr =(int) c;

                if (cur.map.get(intStr) == null){
                    return 0;
                }

                cur = cur.map.get(intStr);
            }

            return cur.end;
        }


        /**
         * 功能描述: 查找前缀
         *
         * @param prefix 前缀
         * @return int
         */
        public int preFind(String prefix){
            if (prefix == null){
                return 0;
            }

            // 从过跟节点开始查找
            Node cur = root;
            char[] charArray = prefix.toCharArray();
            for (char c : charArray) {
                int intStr = (int) c;

                if (cur.map.get(intStr) == null ){
                    return 0;
                }
                cur = cur.map.get(intStr); // 指针后移
            }

            return cur.pass;
        }


        public void delete(String word){
            if (word == null){
                return;
            }

            Node cur = root;
            char[] charArray = word.toCharArray();
            for (char c : charArray) {
                int intStr = (int) c;

                if ((--cur.map.get(intStr).pass) == 0){
                    cur.map.put(intStr,null);
                }

                cur = cur.map.get(intStr);
            }

            cur.end--;
        }
    }

    public static void main(String[] args) {
        TrieUtils trieUtils = new TrieUtils();
        List<String> words = Arrays.asList("abc",
                                           "abd",
                                           "abf",
                                           "abg",
                                           "ab",
                                           "bdf",
                                           "dfa",
                                           "dfd",
                                           "我",
                                           "是",
                                           "人"
        );

        for (String word : words) {
            trieUtils.insert(word);
        }
        //System.out.println(1);
        String preFindStr = "ab";
        System.out.println(String.format("以 %s 为前缀出现的次数为 %d",preFindStr,trieUtils.preFind(preFindStr)));

        preFindStr ="df";
        System.out.println(String.format("以 %s 为前缀出现的次数为 %d",preFindStr,trieUtils.preFind(preFindStr)));

        preFindStr ="b";
        System.out.println(String.format("以 %s 为前缀出现的次数为 %d",preFindStr,trieUtils.preFind(preFindStr)));

        preFindStr ="c";
        System.out.println(String.format("以 %s 为前缀出现的次数为 %d",preFindStr,trieUtils.preFind(preFindStr)));
    }
}
